package main

import "fmt"

func main() {
	//fmt.Println(getNextList("aabaabj"))
	fmt.Println(KMP("aabaabj", "aabj"))
}

//
//  getNextList
//  @Description: 获取模式串的next数组
//  @param s： 输入的字符串
//  @return []int：对应的next数组
//
func getNextList(s string) []int {
	var next = make([]int, len(s))
	next[0] = -1 // 人为规定 第一个和第二位为-1,0
	j, k := 0, -1
	for j < len(s)-1 {
		if k == -1 || s[j] == s[k] {
			j++
			k++
			next[j] = k
		} else {
			k = next[k]
		}
	}
	return next
}

func KMP(s string, t string) int {
	nextList := getNextList(t) // 获取模式串的next数组
	i, j := 0, 0               // 都从零开始匹配
	for i < len(s) && j < len(t) {
		if j == -1 || s[i] == t[j] { // l = -1 表示匹配的子串只有一个元素
			i++ // 后移动
			j++
		} else {
			j = nextList[j] // j 回退
		}
	}
	if j >= len(t) {
		return i - len(t)
	}
	return -1 // 没找到
}
